docs/Interpolation (in-place) sort.htm

   1 <HEAD>
   2 <TITLE>Interpolation (in-place) sort
   3 </TITLE>
   4 <BODY>
   5 <H2>
   6 <H3>
   7 <A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
   8 <A HREF="../../hbook.html">
   9 <IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4 ALT = "[Home]"></A><BR>
  10 <A HREF="../../expand.html">
  11 <IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4 ALT = "[Contents]"></A><BR>
  12 <A HREF="../../sort_a.html">
  13 <IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4 ALT = "[Chapter]"></A><BR>
  14 <A HREF="416.sort.c.html"><IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4 ALT = "[Previous Algorithm]"></A><BR>
  15 <A HREF="417.sort.c.html">
  16 <IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4 ALT = "[Next Algorithm]"></A><BR>
  17 </A>
  18 <BR></H2>
  19 <HR>
  20 <H2><B>Interpolation (in-place) sort
  21 </B></H2><BR>
  22 <CENTER>
  23 <TABLE BORDER>
  24 <TR>
  25 <TD COLSPAN = 1>
  26 <TD rowspan = 1>
  27 <TR><TD>
  28 <XMP>
  29      sort( r, lo, up )
  30      ArrayToSort r;
  31      int lo, up;
  32
  33      {ArrayIndices iwk;
  34      ArrayEntry tempr;
  35      int i, j;
  36
  37      for (i=lo; i<=up; i++)   {iwk[i] = 0;   r[i].k = -r[i].k;}
  38      iwk[lo] = lo-1;
  39      for (i=lo; i<=up; i++)   iwk[ phi(-r[i].k,lo,up) ]++;
  40      for (i=lo; i<up;  i++)   iwk[i+1] += iwk[i];
  41      for (i=up; i>=lo; i--)   if ( r[i].k<0 )
  42           do   {
  43                r[i].k = -r[i].k;
  44                j = iwk[ phi( r[i].k, lo, up ) ]--;
  45                tempr = r[i];
  46                r[i] = r[j];
  47                r[j] = tempr;
  48                } while ( i != j );
  49      for ( i=up-1; i>=lo; i-- ) {
  50           tempr = r[i];
  51           for ( j=i+1; j<=up && (tempr.k>r[j].k); j++ )
  52                r[j-1] = r[j];
  53           r[j-1] = tempr;
  54           }
  55      };
  56 </XMP></TD></TR></TABLE>
  57 <BR>
  58 <H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/416b.sort.c"><IMG SRC="../../images/ftp.xbm" hspace=10>C</A> source (416b.sort.c)  </H3></CENTER>
  59 <HR><H4>
  60 <IMG SRC="../../images/aw3.gif" align=left><H5><BR>
  61 &copy <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
  62 </H5></H4><HR>
  63 </BODY>